package math;

public class SquareRoot {

	private final static int MAX_SQUARE_ROOT = 46340;
	
	// this method will find floor of square root of given int
	// the max number that can be passed to is Integer.MAX_VALUE
	public static int findSquareRoot(int num){

		// square root for negative number is not defined
		if(num < 0) return -1;

		int begin = 0;
		
		// max value possible of floor of square root which is actually
		// floor of Math.sqrt(Integer.MAX_VALUE)
		int end = MAX_SQUARE_ROOT;
		
		// binary search operation starts
		while(begin <= end){
			int mid = begin + (end - begin) / 2;
			
			if(mid == MAX_SQUARE_ROOT){
				return MAX_SQUARE_ROOT;
			}

			// only when mid is not last index
			int midSquare = mid * mid;
			int nextSquare = (mid+1)*(mid+1);
			
			if(num >= midSquare && num < nextSquare){
				return mid;
			}else if(midSquare > num){
				end = mid - 1;
			}else{
				begin = mid + 1;
			}
		}
		
		return -1;
	}
}